1. Field of the Invention
The present invention relates to the field of computer networking, specifically to the field of data communications in a private or public packet networks. More specifically, the present invention relates to a method and apparatus for transmitting cells through a switch from a source to a destination.
2. Description of Related Art
Asynchronous Transfer Mode and other packet networks are characterized by high-speed switches that act to switch data cells of a fixed size and format through the network. Typically, networks communicate using data cells that are relatively short fixed length packets of data that carry voice, video, and computer data across networks at high-speeds relative to the speeds of traditional data networks such as Ethernet, Token Ring, and Fiber Distributed Data Interface (FDDI) Networks. A typical cell is 53 bytes long wherein 5 bytes are for header information and 48 bytes are for data. Often times, however, variations of the same are provided wherein the cell length is modified for different reasons. For example, in one fixed length packet network, a 4-byte header is used and 76 bytes of data are used. This particular cell size is advantageous in that it allows for carrying even multiples of Ethernet data packets.
Traditional local area networks (LANs) operate over shared media. All network devices on a particular network segment must share media with each other so that each device is provided with only a fraction of the total bandwidth of the media. Newer generation intelligent hubs support multiple segments of different types of lands across their back planes to permit LANs to be segmented so that each network device is provided with greater bandwidth. Such hubs provide for a dedicated LAN interface so that, for example, in the case of an Ethernet LAN, a single network device is provided with the full 10 Mb/s bandwidth of the LAN segment. Each port on the hub is connected internally within the hub; typically, by either a high-speed bus or a cross connect.
Such hubs may be known as switching hubs. Generally a switching hub acts to concentrate wiring for a communications network in a central location such as a facilities telephone-wiring closet. The hub comprises a cabinet having multiple ports wherein each port supports one LAN segment. Each area local area network may support multiple network devices such an end user systems that may communicate over the local area network.
Such hub architectures are limited in that they can not scale to the high bandwidths required for integrated networks that transmit real time voice, video, and data. Fixed length packet networks, however, are capable of providing the bandwidth and throughput required for such applications. Such networks are capable of transmitting integrated voice, video, and data traffic because, as described above, they use small fixed size cells. By transmitting small fixed sized cells, these networks overcome delays associated with transmitting relatively large, variable length packets as experienced in traditional data networks. Accordingly, fixed packet length networks greatly increase transmission efficiencies.
Standards have been adopted for ATM networks, for example, by the international telegraph and telephone consultive committee (CCITT). The ATM forum, a group of telecommunications and data networking companies formed to insure the interoperability of public and private ATM implementations facilitates, clarifies, and adopts ATM standards.
The ATM standards are defined with respect to a user-to-network interface (UNI) and a network-to-network interface (NNI). Thus, UNI refers to an interface between a network device such an end user system and an ATM switch. ATM switches transmit information in fixed sized cells, which are formed of well defined, and size limited header areas and user information areas as described before. ATM switches utilize a variety of switching architectures, including, for example, matrix switching architectures back plane bus architectures, and other architectures. The two primary tasks that are generally accomplished by an ATM switch include the translation of path information and the transport of ATM cells of an input port to an output port.
A switch is typically constructed of a plurality of switching elements that act together to transport a cell from the input switch to the correct output. Various types of switching elements are well known such as the matrix switching element and the back plane bus switching elements mentioned before. Each is well known to those of the ordinary skill in the art and each carry out the two above-mentioned tasks.
In a traditional fixed length packet switch, a data packet is received from an external network, e.g. an Ethernet switch, where it is temporarily stored in a buffer. After a plurality of packets have been received, the packets are formed into a cell and then transmitted from an input stage to an intermediate stage where a plurality of cells are combined to create a stream of cells that are transmitted to the switching fabric itself. The switching fabric then receives the stream of cells, stores it in a temporary buffer, for example, an SRAM buffer and then transmits it back out from the switching fabric to the intermediate stage where the stream of cells is broken back into individual cells. The individual cells are transmitted to the output end where they are converted back to packets and then transmitted to the appropriate output location. In a conventional system, a cell that is to be transmitted in a multicast format is transmitted once for each destination to which it is to be transmitted. Accordingly, system efficiencies are lost because system resources are used to continuously transmit the same cell of data. Additionally, even with the above described inefficiencies, the throughput capacities of the devices or systems coupled to receive data on a high speed bus cannot process received data at the rate at which the data is being transmitted to the device. One problem that results from the lower throughput rate of the device receiving data is that the receive buffers are not emptied fast enough. When the receive buffers are not emptied at a fast enough rate, a type of blocking known as head of line blocking occurs. Head of line blocking often results in data being discarded. What is needed therefore is a more efficient process for transmitting multicast cells that also addresses the problem of head of line blocking.